Quantization of Binary-Input Discrete Memoryless Channels

摘要

The quantization of the output of a binary-input discrete memoryless channelto a smaller number of levels is considered. An algorithm which finds anoptimal quantizer, in the sense of maximizing mutual information between thechannel input and the quantizer output is given. This result holds forarbitrary channels, in contrast to previous results for restricted channels ora restricted number of quantizer outputs. In the worst case, the algorithmcomplexity is cubic $M^3$ in the number of channel outputs $M$. Optimality isproved using the theorem of Burshtein, Della Pietra, Kanevsky, and N\'adas formappings which minimize average impurity for classification and regressiontrees.